Mô tả

Phép quay phải

Giả sử R0 là nút gốc của cây và có nút con trái là L. Phép quay phải chuyển L thành gốc của cây và gốc R cũ trở thành con phải của cây. Khi đó con phải trước đây của L là LR bị tách khỏi L, để giữ nguyên tính chất của cây nhị phân tìm kiếm, ta phải cho liên kết trái của R trỏ tới LR.Như vậy giả mã của phép quay phải tại gốc T.root của cây T có thể viết như sau

RIGHT-ROTATE(T) R0=T.root; L=R0.Left; If L=NULL then return False R0.Left=L.Right; L.Right=R0; T.root=L;

Phép quay trái

Giả sử R0 là nút gốc của cây và có nút con phải là R. Phép quay phải chuyển R thành gốc của cây và gốc R0 cũ trở thành con trái của cây T. Khi đó con trái trước đây của R là RL bị tách khỏi mối nối trái của R, còn mối nối phải của R0 lại tách khỏi R, do đó ta có thể cho liên kết phải của R0 trỏ tới RL.Như vậy giả mã của phép quay trái tại gốc T.root của cây T có thể viết như sau

LEFT-ROTATE(T) R0=T.root; R =R0.Right; If R=NULL then return False R0.Right=R.Left; R.Left=R0; T.root=R;  

Chú ý

Sau này ta sẽ gọi phép quay cây T tại gốc đơn giản là phép quay cây T.Một số người so sánh phép quay với tính chất kết hợp của phép toán, chẳng hạn phép cộng như hình bên.